package tree

import "container/list"

// recursiveConnect 递归解法
func recursiveConnect(root *BinaryTreeNode) *BinaryTreeNode {
	if nil == root {
		return root
	}
	connect2(root.Left, root.Right)
	return root
}

func connect2(a *BinaryTreeNode, b *BinaryTreeNode) {
	if nil == a || nil == b {
		return
	}

	a.Next = b
	connect2(a.Left, a.Right)
	connect2(b.Left, b.Right)
	connect2(a.Right, b.Left)
}

// loopConnect 非递归解法
func loopConnect(root *BinaryTreeNode) *BinaryTreeNode {
	if nil == root {
		return nil
	}

	queue := list.New()
	queue.PushBack(root)
	var last *BinaryTreeNode

	for queue.Len() > 0 {
		size := queue.Len()
		for ; size > 0; size-- {
			// poll the first element of the queue
			e := queue.Front().Value.(*BinaryTreeNode)
			queue.Remove(queue.Front())
			if nil != last {
				last.Next = e
			}

			if nil != e.Left {
				queue.PushBack(e.Left)
			}

			if nil != e.Right {
				queue.PushBack(e.Right)
			}
			if size == 1 {
				last = nil
			} else {
				last = e
			}
		}
	}
	return root
}
